`
https://leetcode.cn/problems/sudoku-solver/
`

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  let isFound = false

  const backtrack = (index) => {
    if (isFound) return

    const m = 9, n = 9

    // 获取二维坐标
    const i = Math.floor(index / n), j = index % n

    // 找到一个可行解
    if (index === m * n) {
      isFound = true
      return
    }

    // 如果有预设数字，跳过
    if (board[i][j] !== '.') {
      backtrack(index + 1)
      return
    }

    for (let c = 1; c <= 9; c++) {
      let ch = `${c}`;
      // 剪枝：如果遇到不合法的数字，就跳过
      if (!isValid(i, j, ch)) {
        continue;
      }

      // 做选择
      board[i][j] = ch;

      backtrack(index + 1);
      if (isFound) {
        // 如果找到一个可行解，立即结束
        // 不要撤销选择，否则 board[i][j] 会被重置为 '.'
        return;
      }

      // 撤销选择
      board[i][j] = '.';
    }
  }

  const isValid = (r, c, num) => {
    for (let i = 0; i < 9; i++) {
      // 判断行是否存在重复
      if (board[r][i] === num) return false;
      // 判断列是否存在重复
      if (board[i][c] === num) return false;
      // 判断 3 x 3 方框是否存在重复
      if (board[Math.floor(r / 3) * 3 + Math.floor(i / 3)][Math.floor(c / 3) * 3 + i % 3] === num) {
        return false;
      }
    }
    return true;
  }

  backtrack(0)
};